「Luogu P5596」[XR-4]题 解题报告

题面

给定自然数 $a,b$，求满足下列条件的自然数对 $(x,y)$ 的个数：

$$y^2-x^2=ax+b$$

解题思路

数学题=瞎搞

分析

数据范围已经暗示了一切，这是一道推推推公式的题啊

先考虑无数解的情况：

将 $x^2$ 移到右边

$$y^2=x^2+ax+b$$

显然当 $x^2+ax+b$ 为完全平方时有无数解，即 $(\frac a 2)^2=b$ 时有无数解，判断时可以写成 $a^2=4\times b$

接下去考虑其他情况

可以将左边因式分解康康有什么奇怪的东西：

$$y^2-x^2=ax+b$$ $$(y+x)(y-x)=ax+b$$

令 $k=y-x$，则 $y=x+k$，代入：

$$k(2x+k)=ax+b$$

再乘出来：

$$2kx+k^2=ax+b$$

将所有 $x$ 有关项移至左侧，

$$(2k-a)x=b-k^2$$

分参：

$$x=\frac {b-k^2} {2k-a}$$

然后就推不下去

可以注意到，$x$ 应是自然数，所以 $\frac {b-k^2} {2k-a}>0$

可以解一下上述方程：

$$(b-k^2)(2k-a)>0$$

显然可以看出三根分别为 $k_1=-\sqrt b,k_2=\sqrt b,k_3=\frac a 2$

而 $k$ 显然是自然数，$k_1=-\sqrt b$ 就不要管了，那么有效的范围应该是：

$$k\in (\frac a 2,\sqrt b)\ or\ (\sqrt b,\frac a 2)$$

反正是个奇奇怪怪的东西，幸好范围都不大，直接暴力枚举即可

warning

1、记得开 $long\ long$

1、记得开 $long\ long$

（什么是人类的本质

#include<bits/stdc++.h>
#define rgt register
#define LL long long
#define rll rgt LL
using namespace std;
LL a,b,ans,x,L,R;
int main()
{
    rll k=0;scanf("%lld%lld",&a,&b);
    if(a*a==4*b){printf("inf");return 0;}
    x=sqrt(b);if(x*x==b) ans=1;
    while(1) {++k;L=2*k-a,R=b-k*k;//懒得判断区间左右端点大小，直接暴力枚举就好了，
        if(((L>0&&R>0)||(L<0&&R<0))&&(R%L==0)) ++ans;
        if(R<0&&L>0) break;//当R<0&&L>0时，再也不可能有解，因为两端始终保持异号状态
    }
    printf("%lld\n",ans);//貌似这里都不用开LL..
    return 0;
}